﻿using System;
using System.Collections.Generic;
using System.Text;
using Common.Utilities;

namespace Workflows.Components.TextMining.Clustering
{
    /// <summary>
    /// 
    /// </summary>
    public class HierarchicalCluster:IDocumentCluster
    {
        #region fields
        private Dictionary<int, Dictionary<int, DocTermFreq>> _DocTerms;
        private Dictionary<string, List<int>> _TermStemmings2;
        private Dictionary<int, string> _TermStemmings1;
        private int _NGramLen = 0;

        private IDistanceCalculator _DistanceCalculator;
        private IPurityCalculator _PurityCalculator;
        private Dictionary<int, double> _TermWeights;
        private Dictionary<string, double> _DocDocDistances;           // docid-docid -> distance
        private Dictionary<string, double> _ClusterDocDistances;        // clusterid-docid -> distance
        private Dictionary<string, double> _ClusterClusterDistances;    // clusterid-clusterid -> distance
        private Dictionary<int, List<int>> _ClusterTerms;       // cluster id -> terms
        private List<int> _RemainingDocIDs;
        private Dictionary<int, ClusterNode> _ClusterResult;
        private List<int> _RootClusterIDs;

        private bool _CanOverlap;
        private double _ReassociationDistanceRatio = 1.50;
        private int _MaxIterationCount = 10;
		private double _TermFreqThreshold;
		private double _TermCoverageThreshold;
		private double _ClusterDistanceThreshold;
        #endregion

        #region IDocumentCluster Members
		/// <summary>
		/// 
		/// </summary>
    	public double ClusterDistanceThreshold
    	{
    		get { return _ClusterDistanceThreshold; }
    	}

		/// <summary>
		/// 
		/// </summary>
    	public double TermCoverageThreshold
    	{
    		get { return _TermCoverageThreshold; }
    	}

		/// <summary>
		/// 
		/// </summary>
    	public double TermFreqThreshold
    	{
    		get { return _TermFreqThreshold; }
    	}

    	public event ClusterStatusChanged OnClusterStatusChanged;

        public IDistanceCalculator DistanceCalculator
        {
            get { return _DistanceCalculator; }
            set { _DistanceCalculator=value; }
        }

		/// <summary>
		/// 
		/// </summary>
        public IPurityCalculator PurityCalculator
        {
            get { return _PurityCalculator; }
            set { _PurityCalculator=value; }
        }

		/// <summary>
		/// 
		/// </summary>
        public Dictionary<int, double> TermWeights
        {
            get { return _TermWeights; }
            set { _TermWeights = value;}
        }

		/// <summary>
		/// flag to set of an entity can belong to multiple parent
		/// </summary>
        public bool CanOverlap
        {
            get { return _CanOverlap; }
            set { _CanOverlap=value; }
        }

		/// <summary>
		/// 
		/// </summary>
        public double ReassociationRange
        {
            get { return this._ReassociationDistanceRatio; }
            set { this._ReassociationDistanceRatio = value; }
        }

		/// <summary>
		/// 
		/// </summary>
		/// <param name="termCoverageThreshold"></param>
		/// <param name="termFreqThreshold"></param>
		/// <param name="clusterDistanceThreshold"></param>
        public void SetThreshold(double termCoverageThreshold, double termFreqThreshold, double clusterDistanceThreshold)
        {
            this._TermCoverageThreshold = termCoverageThreshold;
            this._TermFreqThreshold = termFreqThreshold;
            this._ClusterDistanceThreshold = clusterDistanceThreshold;
        }

		/// <summary>
		/// 
		/// </summary>
		/// <param name="docTerms"></param>
		/// <param name="useNgram"></param>
		/// <param name="ngramLen"></param>
		/// <returns></returns>
        public Dictionary<int, ClusterNode> ClusterDocuments(
            Dictionary<int, Dictionary<int, DocTermFreq>> docTerms,
            bool useNgram, int ngramLen)
        {
            if (useNgram)
                this._NGramLen = ngramLen;
            return this.ClusterDocuments(docTerms, null, null);
        }

		/// <summary>
		/// 
		/// </summary>
		/// <param name="docTerms"></param>
		/// <param name="termStemmings1"></param>
		/// <param name="termStemmings2"></param>
		/// <returns></returns>
        public Dictionary<int, ClusterNode> ClusterDocuments(
            Dictionary<int, Dictionary<int,DocTermFreq>> docTerms,
            Dictionary<int,string> termStemmings1,
            Dictionary<string,List<int>> termStemmings2)
        {
            this._DocTerms = docTerms;
            this._TermStemmings1 = termStemmings1;
            this._TermStemmings2 = termStemmings2;

            if(this._DistanceCalculator==null)
                throw new Exception("Calculator must be initialized first before calculation");

            this._ClusterResult = new Dictionary<int, ClusterNode>();
            this._RemainingDocIDs=new List<int>();
            foreach(int docID in this._DocTerms.Keys)
            {
                this._RemainingDocIDs.Add(docID);
            }
            this._ClusterTerms=new Dictionary<int, List<int>>();
            this._RootClusterIDs=new List<int>();

            this.InitDistances();
            while(this.CanContinueCluster())
            {
                this.Grow();

                if(this.OnClusterStatusChanged !=null)
                {
                    string msg = string.Format("Hierarchical clustering...");
                    int percent = this._ClusterResult.Count * 100 /(this._DocTerms.Count - 1);
                    this.OnClusterStatusChanged(
                        this._ClusterResult.Count, 
                        this._RemainingDocIDs.Count, msg, percent);
                }
            }

            if (this.CanOverlap)
            {
                int iterationCount = 0;
                int docsReassociated = this.TryReassociateDocs();
                while (docsReassociated > 0)
                {
                    foreach (int clusterID in this._ClusterResult.Keys)
                    {
                        ClusterNode clusterNode = this._ClusterResult[clusterID];
                        this.UpdateClusterDistance(clusterNode);
                    }

                    
                    iterationCount += 1;
                    if (this.OnClusterStatusChanged != null)
                    {
                        string msg =
                            string.Format(
                                "Hierarchical clustering: reassociation iteration {0} of {1}, {2} docs reassociated...",
                                iterationCount, _MaxIterationCount, docsReassociated);
                        int percent = iterationCount*100/_MaxIterationCount;
                        this.OnClusterStatusChanged(this._ClusterResult.Count, 0, msg, percent);
                    }


                    if (iterationCount >= _MaxIterationCount)
                        break;

                    docsReassociated = this.TryReassociateDocs();
                }
            }

            return this._ClusterResult;
        }

        #endregion

        #region pair-wise distance
        private void InitDistances()
        {
            this._DocDocDistances=new Dictionary<string, double>();
            this._ClusterClusterDistances=new Dictionary<string, double>();
            this._ClusterDocDistances=new Dictionary<string, double>();
            int[] docIDs=new int[this._DocTerms.Count];
            this._DocTerms.Keys.CopyTo(docIDs,0);
            for(int i=0;i<docIDs.Length;i++)
            {
                int docID1 = docIDs[i];
                //Dictionary<int, int> termFreq1 = new Dictionary<int, int>();
                Dictionary<int, DocTermFreq> termFreqs1 = this._DocTerms[docID1];
                //foreach (int termID1 in termFreqs1.Keys)
                //{
                //    termFreq1.Add(termID1, termFreqs1[termID1].Count);
                //}
                for(int k=i+1;k<docIDs.Length;k++)
                {
                    int docID2 = docIDs[k];
                    //Dictionary<int, int> termFreq2 = new Dictionary<int, int>();
                    Dictionary<int, DocTermFreq> termFreqs2 = this._DocTerms[docID2];
                    //foreach (int termID2 in termFreqs2.Keys)
                    //{
                    //    termFreq2.Add(termID2, termFreqs2[termID2].Count);
                    //}
                    Dictionary<int, int> sharedTermIDs = new Dictionary<int, int>();
                    // double distance = this._DistanceCalculator.CalculateDistance(termFreq1, termFreq2, ref sharedTermIDs);
                    double distance;
                    if (this._TermWeights == null || this._TermWeights.Count == 0)
                        distance =
                            this._DistanceCalculator.CalculateDistance(
                                termFreqs1, termFreqs2, ref sharedTermIDs);
                    else if (this._TermStemmings1 == null || this._TermStemmings2 == null)
                        distance = this._DistanceCalculator.CalculateDistance(
                            termFreqs1, termFreqs2, this._TermWeights,
                            true, this._NGramLen, ref sharedTermIDs);
                    else
                        distance = this._DistanceCalculator.CalculateDistance(
                            termFreqs1, termFreqs2, TermWeights,
                            this._TermStemmings1, this._TermStemmings2, ref sharedTermIDs);
                    this._DocDocDistances.Add(string.Format("{0}-{1}",docID1,docID2),distance);
                }
            }
        }

        //private Dictionary<int, int> InitTermFrequency(Dictionary<int, DocTermFreq> termFreqs)
        //{
        //    Dictionary<int, int> termFreq = new Dictionary<int, int>();
        //    if (termFreqs != null && termFreqs.Count > 0)
        //    {
        //        foreach (int termID in termFreqs.Keys)
        //        {
        //            termFreq.Add(termID, termFreqs[termID].Count);
        //        }
        //    }
        //    return termFreq;
        //}
        
        #endregion

        #region search next best doc
        private bool CanContinueCluster()
        {
            if(this._RemainingDocIDs.Count>0)
                return true;
            if(this._RootClusterIDs.Count >1)
                return true;
            return false;
        }

        private void Grow()
        {
            double distance = double.PositiveInfinity;
            int itemID1 = 0;
            int itemID2 = 0;
            bool item1IsCluster = false;
            bool item2IsCluster = false;
            // doc-doc
            foreach(int docID1 in this._RemainingDocIDs)
            {
                foreach(int docID2 in this._RemainingDocIDs)
                {
                    if(docID1!=docID2)
                    {
                        double docdocDistance = 1;
                        if(this._DocDocDistances.ContainsKey(docID1.ToString()+"-"+docID2.ToString()))
                        {
                            docdocDistance = this._DocDocDistances[docID1.ToString() + "-" + docID2.ToString()];
                        }
                        else if (this._DocDocDistances.ContainsKey(docID2.ToString() + "-" + docID1.ToString()))
                        {
                            docdocDistance = this._DocDocDistances[docID2.ToString() + "-" + docID1.ToString()];
                        }
                        if(docdocDistance < distance)
                        {
                            distance = docdocDistance;
                            itemID1 = docID1;
                            itemID2 = docID2;
                            item1IsCluster = false;
                            item2IsCluster = false;
                        }
                    }
                }
            }
            // doc-cluster 
            foreach(int docID in this._RemainingDocIDs)
            {
                foreach (int clusterID in this._RootClusterIDs)
                {
                    if(this._ClusterDocDistances.ContainsKey(clusterID.ToString()+"-"+docID.ToString()))
                    {
                        double clusterDocDistance =
                            this._ClusterDocDistances[clusterID.ToString() + "-" + docID.ToString()];
                        if(clusterDocDistance<distance)
                        {
                            distance = clusterDocDistance;
                            itemID1 = docID;
                            item1IsCluster = false;
                            itemID2 = clusterID;
                            item2IsCluster = true;
                        }
                    }
                }
            }
            // cluster-cluster 
            foreach (int clusterID1 in this._RootClusterIDs)
            {
                foreach (int clusterID2 in this._RootClusterIDs)
                {
                    if (clusterID1 != clusterID2)
                    {
                        if (
                            this._ClusterClusterDistances.ContainsKey(clusterID1.ToString() + "-" +
                                                                      clusterID2.ToString()))
                        {
                            double clusterClusterDistance =
                                this._ClusterClusterDistances[clusterID1.ToString() + "-" + clusterID2.ToString()];
                            if (clusterClusterDistance < distance)
                            {
                                distance = clusterClusterDistance;
                                itemID1 = clusterID1;
                                item1IsCluster = true;
                                itemID2 = clusterID2;
                                item2IsCluster = true;
                            }
                        }
                        else if (
                            this._ClusterClusterDistances.ContainsKey(clusterID2.ToString() + "-" +
                                                                      clusterID1.ToString()))
                        {
                            double clusterClusterDistance =
                                this._ClusterClusterDistances[clusterID2.ToString() + "-" + clusterID1.ToString()];
                            if (clusterClusterDistance < distance)
                            {
                                distance = clusterClusterDistance;
                                itemID1 = clusterID1;
                                item1IsCluster = true;
                                itemID2 = clusterID2;
                                item2IsCluster = true;
                            }
                        }
                    }
                }
            }
            if(distance<double.PositiveInfinity && itemID1 >0 && itemID2>0)
            {
                if (item1IsCluster && item2IsCluster)
                {
                    this.MergeClusterPair(itemID1, itemID2, distance);
                }
                else if(!item1IsCluster && !item2IsCluster)
                {
                    this.MergeDocPair(itemID1, itemID2, distance);
                }
                else if(item1IsCluster && !item2IsCluster)
                {
                    this.MergeDocAndCluster(itemID2, itemID1, distance);
                }
                else
                {
                    this.MergeDocAndCluster(itemID1, itemID2, distance);
                }
            }
        }

        private void MergeDocPair(int docID1, int docID2, double distance)
        {
            this._RemainingDocIDs.Remove(docID1);
            this._RemainingDocIDs.Remove(docID2);

            int clusterID = this.NextClusterID();
            List<int> unionTermIDs=new List<int>();
            Dictionary<int,DocTermFreq> termFreqs1 = this._DocTerms[docID1];
            int[] termIDs1=new int[termFreqs1.Count];
            termFreqs1.Keys.CopyTo(termIDs1,0);
            unionTermIDs.AddRange(termIDs1);
            Dictionary<int, DocTermFreq> termFreqs2 = this._DocTerms[docID2];
            foreach (int termID2 in termFreqs2.Keys)
            {
                if(!unionTermIDs.Contains(termID2))
                {
                    unionTermIDs.Add(termID2);
                }
            }
            this._ClusterTerms.Add(clusterID,unionTermIDs);
            distance = distance/2;
            ClusterNode clusterNode = new ClusterNode();
            clusterNode.ClusterID = clusterID;
            clusterNode.DocIDs=new List<int>();
            clusterNode.DocIDs.Add(docID1);
            clusterNode.DocIDs.Add(docID2);
            clusterNode.Distance = distance;
            clusterNode.SupportiveTermWeights = new Dictionary<int, double>();
            foreach(int termID in unionTermIDs)
            {
                if(termFreqs1.ContainsKey(termID) && termFreqs2.ContainsKey(termID))
                {
                    double weight = termFreqs1[termID].Weight*termFreqs1[termID].Count +
                                    termFreqs2[termID].Count*termFreqs2[termID].Weight;
                    clusterNode.SupportiveTermWeights.Add(termID, weight);
                }
            }
            //clusterNode.LeftChildID = docID1;
            //clusterNode.LeftChildIsCluster = false;
            //clusterNode.RightChildID = docID2;
            //clusterNode.RightChildIsCluster = false;
            this._ClusterResult.Add(clusterID,clusterNode);
            this.UpdateClusterDistances(clusterID);
            if(!this._RootClusterIDs.Contains(clusterID))
                this._RootClusterIDs.Add(clusterID);
        }

        private void MergeClusterPair(int clusterID1, int clusterID2, double distance)
        {
            int clusterID = this.NextClusterID();
            List<int> unionTermIDs = new List<int>();
            List<int> termIDs1 = this._ClusterTerms[clusterID1];
            unionTermIDs.AddRange(termIDs1.ToArray());
            List<int> termIDs2 = this._ClusterTerms[clusterID2];
            foreach (int termID2 in termIDs2)
            {
                if (!unionTermIDs.Contains(termID2))
                {
                    unionTermIDs.Add(termID2);
                }
            }
            this._ClusterTerms.Add(clusterID, unionTermIDs);
            distance = distance / 2;
            ClusterNode clusterNode = new ClusterNode();
            clusterNode.ClusterID = clusterID;
            clusterNode.DocIDs = new List<int>();
            clusterNode.ChildClusterIDs=new List<int>();
            clusterNode.ChildClusterIDs.Add(clusterID1);
            clusterNode.ChildClusterIDs.Add(clusterID2);
            clusterNode.Distance = distance;
            clusterNode.SupportiveTermWeights=new Dictionary<int, double>();
            foreach(int termID in unionTermIDs)
            {
                if(termIDs1.Contains(termID) && termIDs2.Contains(termID))
                {
                    clusterNode.SupportiveTermWeights.Add(termID, 2);
                }
            }
            //clusterNode.LeftChildID = clusterID1;
            //clusterNode.LeftChildIsCluster = true;
            //clusterNode.RightChildID = clusterID2;
            //clusterNode.RightChildIsCluster = true;
            this._ClusterResult.Add(clusterID, clusterNode);
            this.UpdateClusterDistances(clusterID);

            this._RootClusterIDs.Remove(clusterID1);
            this._RootClusterIDs.Remove(clusterID2);
            this._RootClusterIDs.Add(clusterID);
        }

        private void MergeDocAndCluster(int docID, int childClusterID, double distance)
        {
            this._RemainingDocIDs.Remove(docID);
            int newClusterID = this.NextClusterID();
            List<int> unionTermIDs = new List<int>();
            Dictionary<int,DocTermFreq> termFreqs1 = this._DocTerms[docID];
            int[] termIDs1=new int[termFreqs1.Count];
            termFreqs1.Keys.CopyTo(termIDs1,0);
            unionTermIDs.AddRange(termIDs1);
            List<int> termIDs2 = this._ClusterTerms[childClusterID];
            foreach (int termID2 in termIDs2)
            {
                if (!unionTermIDs.Contains(termID2))
                {
                    unionTermIDs.Add(termID2);
                }
            }
            this._ClusterTerms.Add(newClusterID, unionTermIDs);
            distance = distance / 2;
            ClusterNode clusterNode = new ClusterNode();
            clusterNode.ClusterID = newClusterID;
            clusterNode.DocIDs = new List<int>();
            clusterNode.DocIDs.Add(docID);
            clusterNode.ChildClusterIDs=new List<int>();
            clusterNode.ChildClusterIDs.Add(childClusterID);
            clusterNode.Distance = distance;
            clusterNode.SupportiveTermWeights=new Dictionary<int, double>();
            foreach(int termID in unionTermIDs)
            {
                if(termFreqs1.ContainsKey(termID) && termIDs2.Contains(termID))
                {
                    double weight = termFreqs1[termID].Count * termFreqs1[termID].Weight + 1;
                    clusterNode.SupportiveTermWeights.Add(termID, weight);
                }
            }
            //clusterNode.LeftChildID = childClusterID;
            //clusterNode.LeftChildIsCluster = true;
            //clusterNode.RightChildID = docID;
            //clusterNode.RightChildIsCluster = false;
            this._ClusterResult.Add(newClusterID, clusterNode);
            this.UpdateClusterDistances(newClusterID);

            this._RootClusterIDs.Remove(childClusterID);
            this._RootClusterIDs.Add(newClusterID);
        }

        private int NextClusterID()
        {
            int lastClusterID = 0;
            if (this._ClusterResult.Count > 0)
            {
                foreach(int clusterID in this._ClusterResult.Keys)
                {
                    if(clusterID > lastClusterID)
                        lastClusterID = clusterID;
                }
            }
            return lastClusterID + 1;
        }

        /// <summary>
        /// update cluster-cluster, cluster-doc distances stored in memory 
        /// that are affected by newly created cluster
        /// </summary>
        /// <param name="newClusterID"></param>
        private void UpdateClusterDistances(int newClusterID)
        {
            Dictionary<int, DocTermFreq> termFreqs1 = new Dictionary<int, DocTermFreq>();
            List<int> docIDs = this.GetDocsForCluster(newClusterID);

            foreach (int docID1 in docIDs)
            {
                Dictionary<int, DocTermFreq> docTerms1 = this._DocTerms[docID1];
                foreach (int termID in docTerms1.Keys)
                {
                    if (termFreqs1.ContainsKey(termID))
                    {
                        DocTermFreq docTermFreq1 = termFreqs1[termID];
                        docTermFreq1.Count += docTerms1[termID].Count;
                        termFreqs1[termID] = docTermFreq1;
                    }
                    else
                    {
                        termFreqs1.Add(termID, docTerms1[termID]);
                    }
                }
            }
            // termFreq1.Add(termID1, 1);
            

            // update cluster - doc distances 
            foreach(int docID in this._RemainingDocIDs)
            {
                Dictionary<int, DocTermFreq> termFreqs2 = this._DocTerms[docID];
                //Dictionary<int,int> termFreq2=new Dictionary<int, int>();
                //foreach(int termID2 in termFreqs2.Keys)
                //{
                //    termFreq2.Add(termID2,1);
                //}
                Dictionary<int, int> sharedTermIDs = new Dictionary<int, int>();
                double distance;
                if (this._TermWeights == null || this._TermWeights.Count == 0)
                    distance =
                        this._DistanceCalculator.CalculateDistance(
                            termFreqs1, termFreqs2, ref sharedTermIDs);
                else if (this._TermStemmings1 == null || this._TermStemmings2 == null)
                    distance = this._DistanceCalculator.CalculateDistance(
                        termFreqs1, termFreqs2, this._TermWeights,
                        true, this._NGramLen, ref sharedTermIDs);
                else
                    distance = this._DistanceCalculator.CalculateDistance(
                        termFreqs1, termFreqs2, TermWeights,
                        this._TermStemmings1, this._TermStemmings2, ref sharedTermIDs);
                this._ClusterDocDistances.Add(newClusterID.ToString() + "-" + docID.ToString(), distance);
            }

            // update cluster - cluster distances 
            foreach(int clusterID in this._ClusterTerms.Keys)
            {
                if(clusterID !=newClusterID)
                {
                    // List<int> termIDs2 = this._ClusterTerms[clusterID];
                    Dictionary<int, DocTermFreq> termFreqs2 = new Dictionary<int, DocTermFreq>();
                    //foreach (int termID2 in termIDs2)
                    //{
                    //    termFreq2.Add(termID2, 1);
                    //}
                    ClusterNode clusterNode2=this._ClusterResult[clusterID];
                    foreach (int docID2 in clusterNode2.DocIDs)
                    {
                        Dictionary<int, DocTermFreq> docTerms = this._DocTerms[docID2];
                        foreach (int termID in docTerms.Keys)
                        {
                            if (termFreqs2.ContainsKey(termID))
                            {
                                DocTermFreq docTermFreq = termFreqs2[termID];
                                docTermFreq.Count += docTerms[termID].Count;
                                termFreqs2[termID] = docTermFreq;
                            }
                            else
                            {
                                termFreqs2.Add(termID, docTerms[termID]);
                            }
                        }
                    }
                    Dictionary<int, int> sharedTermIDs = new Dictionary<int, int>();
                    //double distance = this._DistanceCalculator.CalculateDistance(termFreq1, termFreq2, ref sharedTermIDs);
                    double distance;
                    if (this._TermWeights == null || this._TermWeights.Count == 0)
                        distance =
                            this._DistanceCalculator.CalculateDistance(
                                termFreqs1, termFreqs2, ref sharedTermIDs);
                    else if (this._TermStemmings1 == null || this._TermStemmings2 == null)
                        distance = this._DistanceCalculator.CalculateDistance(
                            termFreqs1, termFreqs2, this._TermWeights,
                            true, this._NGramLen, ref sharedTermIDs);
                    else
                        distance = this._DistanceCalculator.CalculateDistance(
                            termFreqs1, termFreqs2, TermWeights,
                            this._TermStemmings1, this._TermStemmings2, ref sharedTermIDs);
                    this._ClusterClusterDistances.Add(clusterID.ToString() + "-" + newClusterID.ToString(), distance);
                }
            }
        }

        private List<int> GetDocsForCluster(int clusterID)
        {
            ClusterNode clusterNode = this._ClusterResult[clusterID];
            List<int> docIDs =new List<int>();
			if (clusterNode.DocIDs != null && clusterNode.DocIDs.Count > 0)
				docIDs.AddRange(clusterNode.DocIDs);
            if(clusterNode.ChildClusterIDs !=null && clusterNode.ChildClusterIDs.Count>0)
            {
                foreach(int childClusterID in clusterNode.ChildClusterIDs)
                {
                    List<int> childDocIDs = this.GetDocsForCluster(childClusterID);
                    foreach(int childDocID in childDocIDs)
                    {
                        if(!docIDs.Contains(childDocID))
                            docIDs.Add(childDocID);
                    }
                }
            }
            return docIDs;
        }
        #endregion

        #region re-association
        private int TryReassociateDocs()
        {
            int[] docIDs = new int[this._DocTerms.Count];
            this._DocTerms.Keys.CopyTo(docIDs, 0);
            int[] clusterIDs = new int[this._ClusterResult.Count];
            this._ClusterResult.Keys.CopyTo(clusterIDs, 0);
            int numDocsReassociated = 0;
            for (int i = 0; i < docIDs.Length; i++)
            {
                int docID = docIDs[i];
                List<int> oldClusterIDs=new List<int>();
                for (int k = 0; k < clusterIDs.Length; k++)
                {
                    ClusterNode clusterNode = this._ClusterResult[clusterIDs[k]];
                    if (clusterNode.DocIDs.Contains(docID))
                    {
                        oldClusterIDs.Add(clusterIDs[k]);
                        break;
                    }
                }
                ClusterNode oldCluster = this._ClusterResult[oldClusterIDs[0]];
                double oldDocClusterDistance = this.CalculateDocClusterDistance(docID, oldCluster);
                for (int k = 0; k < clusterIDs.Length; k++)
                {
                    if (!oldClusterIDs.Contains(clusterIDs[k]))
                    {
                        ClusterNode clusterNode = this._ClusterResult[clusterIDs[k]];
                        double newDistance = this.CalculateDocClusterDistance(docID, clusterNode);
                        if (newDistance <= oldDocClusterDistance*this._ReassociationDistanceRatio &&
                            newDistance <= clusterNode.Distance*this._ReassociationDistanceRatio)
                        {
                            if (!clusterNode.DocIDs.Contains(docID))
                            {
                                clusterNode.DocIDs.Add(docID);
                                numDocsReassociated += 1;
                                break;
                            }
                        }
                    }
                }
            }
            return numDocsReassociated;
        }

        /// <summary>
        /// cluster distance is recalculated, average of all doc-doc distances within the cluster
        /// </summary>
        /// <param name="clusterNode"></param>
        private void UpdateClusterDistance(ClusterNode clusterNode)
        {
            List<double> clusterDistances = new List<double>();
            Dictionary<int, double> supportiveTermWeights = new Dictionary<int, double>();
            for (int i = 0; i < clusterNode.DocIDs.Count; i++)
            {
                //int docID1 = clusterNode.DocIDs[i];
                //List<double> docDistances = new List<double>();
                Dictionary<int, DocTermFreq> termFreqs1 = this._DocTerms[clusterNode.DocIDs[i]];
                //Dictionary<int, int> termFreq1 = this.InitTermFrequency(termFreqs1);
                for (int k = 0; k < clusterNode.DocIDs.Count; k++)
                {
                    if (k != i)
                    {
                        // int docID2 = clusterNode.DocIDs[k];
                        Dictionary<int, DocTermFreq> termFreqs2 = this._DocTerms[clusterNode.DocIDs[k]];
                        //Dictionary<int, int> termFreq2 = this.InitTermFrequency(termFreqs2);
                        Dictionary<int, int> sharedTermIDs = new Dictionary<int, int>();
                        double distance=0;
                        if (this._TermWeights == null || this._TermWeights.Count == 0)
                            distance =
                                this._DistanceCalculator.CalculateDistance(
                                    termFreqs1, termFreqs2, ref sharedTermIDs);
                        else if (this._TermStemmings1 == null || this._TermStemmings2 == null)
                            distance = this._DistanceCalculator.CalculateDistance(
                                termFreqs1, termFreqs2, this._TermWeights,
                                true, this._NGramLen, ref sharedTermIDs);
                        else
                            distance = this._DistanceCalculator.CalculateDistance(
                                termFreqs1, termFreqs2, TermWeights,
                                this._TermStemmings1, this._TermStemmings2, ref sharedTermIDs);
                        clusterDistances.Add(distance);
                        //docDistances.Add(distance);

                        if (sharedTermIDs.Count > 0)
                        {
                            foreach (int sharedTermID in sharedTermIDs.Keys)
                            {
                                double weight = 0;
                                if(termFreqs1.ContainsKey(sharedTermID))
                                {
                                    weight = termFreqs1[sharedTermID].Count*termFreqs1[sharedTermID].Weight;    
                                }
                                if(termFreqs2.ContainsKey(sharedTermID))
                                {
                                    weight += termFreqs2[sharedTermID].Count * termFreqs2[sharedTermID].Weight;
                                }
                                                
                                if (supportiveTermWeights.ContainsKey(sharedTermID))
                                {
                                    supportiveTermWeights[sharedTermID] = supportiveTermWeights[sharedTermID] + weight;
                                }
                                else
                                {
                                    supportiveTermWeights.Add(sharedTermID, weight);
                                }
                            }
                        }
                    }
                }
                // if single doc, the distance is 0
                //if (docDistances.Count == 0)
                //    docDistances.Add(0);
                //if (this._DocDistances.ContainsKey(docID1))
                //{
                //    this._DocDistances[docID1] = StatsUtil.GetAverage(docDistances);
                //}
                //else
                //{
                //    this._DocDistances.Add(docID1, StatsUtil.GetAverage(docDistances));
                //}
            }
            if (clusterDistances.Count == 0)
                clusterDistances.Add(0);

            double clusterAvgDistance = StatsUtil.GetAverage(clusterDistances).Value;
            clusterNode.Distance = clusterAvgDistance;
            clusterNode.SupportiveTermWeights = supportiveTermWeights;
        }

        private double CalculateDocClusterDistance(int docID, ClusterNode clusterNode)
        {
            Dictionary<int, DocTermFreq> clusterDocTermFreqs = new Dictionary<int, DocTermFreq>();
            foreach (int docIDInCluster in clusterNode.DocIDs)
            {
                Dictionary<int, DocTermFreq> termFreqs = this._DocTerms[docIDInCluster];
                foreach (int termID in termFreqs.Keys)
                {
                    if (!clusterDocTermFreqs.ContainsKey(termID))
                    {
                        clusterDocTermFreqs.Add(termID, termFreqs[termID]);
                    }
                    else
                    {
                        DocTermFreq docTermFreq = clusterDocTermFreqs[termID];
                        docTermFreq.Count += termFreqs[termID].Count;
                        clusterDocTermFreqs[termID] = docTermFreq;
                    }
                }
            }

            Dictionary<int, DocTermFreq> termFreqs1 = this._DocTerms[docID];
            //Dictionary<int, int> termFreq1 = this.InitTermFrequency(termFreqs1);
            //Dictionary<int, int> termFreq2 = this.InitTermFrequency(clusterDocTermFreqs);
            Dictionary<int, int> sharedTermIDs = new Dictionary<int, int>();
            if (this._TermWeights == null || this._TermWeights.Count == 0)
            {
                return this._DistanceCalculator.CalculateDistance(
                    termFreqs1, clusterDocTermFreqs, ref sharedTermIDs);
            }
            else if(this._TermStemmings1==null || this._TermStemmings2==null)
            {
                return this._DistanceCalculator.CalculateDistance(
                    termFreqs1, clusterDocTermFreqs, this._TermWeights,
                    true, this._NGramLen, ref sharedTermIDs);
            }
            else
            {
                return this._DistanceCalculator.CalculateDistance(
                    termFreqs1, clusterDocTermFreqs, this._TermWeights,
                    this._TermStemmings1, this._TermStemmings2, ref sharedTermIDs);
            }
        }
        #endregion
    }
}
